package com.liyghting.datastructurealgorithm.sort;

/**
 * 线性排序 桶排序
 * 核心思想，就是把要排序的数据投放到有序的桶中，每个桶在进行单独的排序（快排，归并等）。桶内排完序后，在把桶内数据按照顺序依次取出，组成的序列就是有序的。
 * 时间复杂度O(n) 适合数据分布范围不大，但是本身数据集比较大
 *
 * 比如根据年龄给100万用户排序？ 解决方法 我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这
 * 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。
 * 1.要排序的数据很容易就划分为M个桶，并且桶与桶之间有着天然的大小顺序。这样桶内数据排完序之后，桶与桶之间的数据不需要在进行排序
 * 2.其次，数据在各个桶之间分布都比较均匀 适合用在外部排序中。外部排序是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中
 * 比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB
 * 的数据都加载到内存中。这个时候该怎么办呢？ 解决方法：遍历订单数据，
 *
 * @author LiYiGuang
 * @date 2020/1/14 10:23
 */
public class BucketSort {
    /**
     * 桶排序
     *
     * @param arr 数组
     * @param bucketSize 桶大小
     */
	public static void bucketSort(int[] arr, int bucketSize) {
		int len = arr.length;
		int min = arr[0];
		int max = arr[0];
		for (int i = 1; i < len; i++) {
			if (min > arr[i]) {
				min = arr[i];
			}
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		// 桶个数
		int bucketCount = (max - min) / bucketSize + 1;
		// 桶初始化
		int[][] bucket = new int[bucketCount][bucketSize];
		// 每个桶中实际的大小
		int[] indexArr = new int[bucketCount];
		// 把要排序的数据放到对应的桶中
		for (int i = 0; i < len; i++) {
			int bucketIndex = (arr[i] - min) / bucketSize;
			if (indexArr[bucketIndex] == bucket[bucketIndex].length) {
				ensureCapacity(bucket, bucketIndex);
			}
			bucket[bucketIndex][indexArr[bucketIndex]++] = arr[i];
		}
		int k = 0;
		for (int i = 0; i < bucketCount; i++) {
		    if (indexArr[i] == 0) continue;
			QuickSort.quickSort(bucket[i], indexArr[i]);
			for (int j = 0; j < indexArr[i]; j++) {
				arr[k++] = bucket[i][j];
			}
		}

	}

	private static void ensureCapacity(int[][] bucket, int bucketIndex) {
		int[] tmpArr = bucket[bucketIndex];
		int[] newArr = new int[tmpArr.length * 2];
		for (int i = 0; i < tmpArr.length; i++) {
			newArr[i] = tmpArr[i];
		}
		bucket[bucketIndex] = newArr;
	}

    public static void print(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = new int[] { 11, 8, 3, 9, 7, 1, 2, 5 };
        bucketSort(arr,2);
        print(arr,8);
    }
}
